#ifndef ORDEREDARRAY_H
#define ORDEREDARRAY_H

#include <stdlib.h>

/**
  This array is insertion sorted - it always remains in a sorted state (between
  calls).
*/
template <class T, u32 N>
class OrderedArray
{
public:
  /**
    Constructor
  **/
  OrderedArray()
  {
    for (int i = 0; i < N; i++)
    {
      array[i] = NULL;
    }
    size = 0;
  }

  ~OrderedArray() {}
  
  /**
    Inserts item into the array at the correct place (sorted).
  **/
  void insert(T item)
  {
    u32 iterator = 0;
    while (iterator < size && array[iterator]<item)
    {
      iterator++;
    }
    if (iterator == size) // just add at end of array
    {
      array[size++] = item;
    }
    else
    {
      T tmp = array[iterator];
      array[iterator] = item;
      while (iterator < size)
      {
        iterator++;
        T tmp2 = array[iterator];
        array[iterator] = tmp;
        tmp = tmp2;
      }
      size++;
    }
  }
  
  /**
    Looks up the item at location idx.
  **/
  T getItem(u32 idx)
  {
    return array[idx];
  }
  
  /**
    Deletes the item at location idx from the array.
  **/
  void remove(u32 idx)
  {
    while (idx < size)
    {
      array[idx] = array[idx+1];
      idx++;
    }
    size--;
  }
  
  u32 getSize()
  {
    return size;
  }

private:
  T array[N];
  u32 size;
};

#endif
